package brinaryTree;

import java.util.*;

/**
 * 501. 二叉搜索树中的众数
 * <p>
 * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 * <p>
 * 如果树中有不止一个众数，可以按 任意顺序 返回。
 * <p>
 * 假定 BST 满足如下定义：
 * <p>
 * 结点左子树中所含节点的值 小于等于 当前节点的值
 * <p>
 * 结点右子树中所含节点的值 大于等于 当前节点的值
 * <p>
 * 左子树和右子树都是二叉搜索树
 */
public class N501_FindModeInBinaryTree {
    private int count;
    private int maxCount;
    private TreeNode pre;
    private List<Integer> res;

    public int[] findMode(TreeNode root) {
        count = 0;
        maxCount = 0;
        pre = null;
        searchBST(root);
        int[] r = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            r[i] = res.get(i);
        }
        return r;
    }

    private void searchBST(TreeNode cur) {

        searchBST(cur.left);

        if (pre == null) count = 1;
        else if (pre.val == cur.val) count++;
        else count = 1;

        pre = cur;

        if (count == maxCount) {
            res.add(cur.val);
        }
        if (count > maxCount) {
            res.clear();
            maxCount = count;
            res.add(cur.val);
        }

        searchBST(cur.right);
    }


    // 普通二叉树求众数 暴力法
    public int[] findMode_violence(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                map.put(node.val, map.getOrDefault(node.val, 0) + 1);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        int max_count = 0;
        for (Integer value : map.values()) {
            max_count = Math.max(value, max_count);
        }
        for (Integer key : map.keySet()) {
            if (map.get(key) == max_count)
                list.add(key);
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}
